I. Technical Field
This application pertains to the compression or encoding of blocks of digital data, and particularly to the compression or encoding of blocks comprising particular distributions of binary values.
II. Related Art and Other Considerations
It is common in packet data transmission to send an acknowledgement of correct receipt of packets back to a transmitter which generated the packets, so that the transmitter may retransmit any packets that were not received correctly. Sometimes, due (for example) to transmission delay, especially through a satellite in orbit, it is not efficient to perform packet-by-packet acknowledgement. Instead, a receiver such as a packet data receiver receives groups of N number of data packets (referred to as “containers”) from an originating transmitter. Using error detection, the receiver classifies each decoded data packet as correct or incorrect. If a packet is correct, the corresponding bit of an N-bit acknowledgement word is set to a first value (e.g., 0), while if the packet is incorrect, the bit is set to a second value (e.g., 1). The receiver then causes an associated transmitter to transmit a coded message to a receiver associated with the originating transmitter in a manner to include or allow reconstruction of the acknowledgement word, and thus to inform the originating transmitter which packets must be resent.
In the prior art, two general method are known for transmitting such acknowledgement words. A first method transmits the entire acknowledgment word, adding a Cyclic Redundancy Check (CRC) code to guard against errors. A second known method employs run-length encoding to compress the acknowledgement word. Run length encoding exploits the expectation that the pattern of errors will be clumped, so that runs of several zeros are expected to be interspersed with runs of several ones. This is indeed the error pattern that would be expected due to a slowly Rayleigh fading signal, as may occur in terrestrial mobile communications. However, in satellite communications operating at marginal signal levels and in a Rician fading environment, the pattern of errors can be different. Errors do not necessarily occur in runs, but rather are randomly distributed.
Nevertheless, if the number of errors is less than some threshold, the number of possible error patterns can be described using less than N-bits, thus allowing greater sized containers to be acknowledged using the same message length.
What is desired, therefore, and an object of the present invention, are one or more of method, apparatus, system, and technique for assigning numbers of less than N bits to particular patterns of K polarity values in N bits, in such a way that the numbers may be easily decoded to reproduce an N-bit word.